"""
139.单词拆分
https://leetcode.cn/problems/word-break/description/

给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。

说明：

拆分时可以重复使用字典中的单词。

你可以假设字典中没有重复的单词。

示例 1：

输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。
示例 2：

输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。
注意你可以重复使用字典中的单词。
示例 3：

输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false

提示：

1 <= s.length <= 300
1 <= wordDict.length <= 1000
1 <= wordDict[i].length <= 20
s 和 wordDict[i] 仅由小写英文字母组成
wordDict 中的所有字符串 互不相同
"""
from typing import List
import math

class Solution:
    """
    字符串看作背包，词典看作物品
    dp[i][j]表示遍历到字符串j位置处，遍历到第i个单词
    此时判断，单词i是否是字符串最后一个单词
        如果是：判断dp[:][j-len(wordDict[i])]是否能拆分成单词
        如果否：判断dp[i-1][j]是否能拆分成单词
    有点类似组合数
    
    外层遍历背包，内层遍历物品
    """
    # 1维DP，惯性思维
    # 复杂度受字典长度影响
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        dp = [False] * (len(s)+1)
        dp[0] = True
        for i in range(1, len(s)+1):
            for j in range(len(wordDict)):
                word = wordDict[j]
                if i < len(word):
                    dp[i] = dp[i]
                elif s[i-len(word):i] == word:
                    dp[i] = dp[i-len(word)] or dp[i]
                else:
                    dp[i] = dp[i]
        return dp[len(s)]
    
    # dp + 双指针，创新做法
    # 双层循环遍历，i和j之间的单词是否在单词表中
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        n = len(s)
        dp = [False] * (n+1)
        dp[0] = True
        for i in range(0, n+1):
            for j in range(i+1, n+1):
                if dp[i] and s[i:j] in wordDict:
                    dp[j] = True
        return dp[n]

if __name__ == "__main__":
    so = Solution()

    s = "applepenapple"
    wordDict = ["apple", "pen"]
    
    # s = "catsandog"
    # wordDict = ["cats", "dog", "sand", "and", "cat"]
    n = so.wordBreak(s, wordDict)
    print(n)